# ------------------------------------------------------------------
# The Computer Language Shootout
# http://shootout.alioth.debian.org/
#
# Contributed by Leo Osvald
# ------------------------------------------------------------------

tree <- function(item, depth) {
    if (depth == 0)
        return(c(item, NA, NA))
    return(list(item,
        tree(2 * item - 1, depth - 1),
        tree(2 * item, depth - 1)))
}

check <- function(atree)
    if(is.na(atree[[2]][[1]])) atree[[1]] else atree[[1]] + check(atree[[2]]) - check(atree[[3]])

binarytrees_naive <- function(n = 10) {

    min_depth <- 4
    max_depth <- max(min_depth + 2, n)
    stretch_depth <- max_depth + 1

    #cat(sep="", "stretch tree of depth ", stretch_depth, "\t check: ",
        chk <- check(tree(0, stretch_depth))
		#, "\n")

    long_lived_tree <- tree(0, max_depth)

    for (depth in (min_depth/2):(max_depth/2)) {
        iterations <- 2^(2*(max_depth - min_depth) - depth )
        chk_sum <- 0
        #for (i in 1:iterations)
        for (i in 1:iterations)
        chk_sum <- chk_sum + check(tree(i, depth)) + check(tree(-i, depth))
        #cat(sep="", iterations * 2, "\t trees of depth ", depth, "\t check ",
        #    chk_sum, "\n")
				chk <- chk + chk_sum
    }

    #cat(sep="", "long lived tree of depth ", max_depth, "\t check: ", 
        chk <- chk + check(long_lived_tree)
		#, "\n")
		chk
}

binarytrees_naive(13)
